package leetcode.editor.cn.dsa24_dijkstra;
//有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
//
// 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样
//的路线，则输出 -1。 
//
// 示例 1： 
//输入:
//n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
//src = 0, dst = 2, k = 1
//输出: 200
//解释: 
//城市航班图如下
//
//从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
//
// 示例 2： 
//输入:
//n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
//src = 0, dst = 2, k = 0
//输出: 500
//解释: 
//城市航班图如下
//
//从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
//
// 提示： 
// n 范围是 [1, 100]，城市标签从 0 到 n - 1
// 航班数量范围是 [0, n * (n - 1) / 2] 
// 每个航班的格式 (src, dst, price) 
// 每个航班的价格范围是 [1, 10000] 
// k 范围是 [0, n - 1] 
// 航班没有重复，且不存在自环 
// 
// Related Topics 堆 广度优先搜索 动态规划 
// 👍 213 👎 0

import java.util.PriorityQueue;

public class CheapestFlightsWithinKStops787 {
    public static void main(String[] args) {
        Solution solution = new CheapestFlightsWithinKStops787().new Solution();
        int[][] arr = {{0,1,100},{1,2,100},{0,2,500}};
        System.out.println(solution.findCheapestPrice(3, arr, 0, 2, 1)); //200
        System.out.println(solution.findCheapestPrice(3, arr, 0, 2, 0)); //500
        int[][] arr2 = {{0,1,1},{0,2,5},{1,2,1},{2,3,1}};
        System.out.println(solution.findCheapestPrice(4, arr2, 0, 3, 1)); //6
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用迪杰斯特拉算法：优先队列(最小堆) + 贪心 + 广度优先搜索
         */
        public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
            // 构建有权图的邻接矩阵
            int[][] graph = new int[n][n];
            for (int[] flight: flights) {
                // [a,b]存储从城市a到城市b航班的价格
                graph[flight[0]][flight[1]] = flight[2];
            }
            // 我们需要存储从源节点src到各个节点的最短距离
            // 由于这里有限制步长，因此需要使用二维数组记录src到各个节点不同步长的最短记录
            int[][] dist = new int[n][K+2]; // 加上终点dst，最大步长可为K+1，因此长度为K+2
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < K+2; j++) {
                    // dist[i][j]表示起点经过j步长到达城市i的最短距离
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
            // 优先队列(最小堆)，按照价格排序
            PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
            // 队列存储[城市city, 中转站k, 起点经过k-1个中转站到该城市最小的价格]
            queue.offer(new int[]{src, 0, 0});
            while (!queue.isEmpty()) {
                int[] info = queue.poll();
                int city = info[0], k = info[1], cost = info[2];
                if (city == dst && k <= K+1) { // 到达终点，当前就是最小价格
                    return cost;
                } else if (k > K) { // 超过限制步长
                    continue;
                }
                for (int i = 0; i < n; i++)
                    if (graph[city][i] > 0) { // 取当前节点的邻居节点
                        int newcost = cost + graph[city][i]; // 到相邻城市的价格
                        if (newcost < dist[i][k+1]) {
                            dist[i][k+1] = newcost; // 当前价格更小则更新最小价格
                            queue.offer(new int[]{i, k+1, newcost}); // 入队
                        }
                    }
            }
            return -1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}